/**
 * backTracking 
 * 回溯算法（递归）: 暴力搜索,解决组合、切割、子集、排列、棋盘问题
 * 组合题目：77 、39 、40 、17 、 216
 * 子集: 78、491
 * 字符串切割： 93 、131
 * 排列: 46 、 47
 * 棋盘问题： 37 、51
 * 
 */
// function backTracking () {
//     // 一般无返回值
//     // 确认参数
//     // 中止条件，搜集结果
//     // 单层搜索逻辑（for 循环）
//     //  for（）{
//     //       1、处理节点
//     //       2、递归
//     //       3、回溯、撤销处理节点
//     // }
// }

// 39.组合总和 combinationSum([2, 3, 6, 7], 7) ==> [[2,2,3],[7]]
const combinationSum = function (candidates, target) {
    candidates.sort((a, b) => a - b)
    const len = candidates.length, res = [], path = []
    const backTracking = function (sum, index) {
        // 中止条件
        if (sum > target) return -1
        if (sum == target) {
            res.push([...path])
            return -1
        }

        for (let i = index; i < len; i++) {
            sum += candidates[i]
            path.push(candidates[i])
            const r = backTracking(sum, i)
            sum -= path.pop()
            if (r == -1) break
        }
    }
    backTracking(0, 0)
    return res
}

// 216.组合总和 III  combinationSum3(3, 9) ==> [ [ 1, 2, 6 ], [ 1, 3, 5 ], [ 2, 3, 4 ] ]
const combinationSum3 = function (k, n) {
    const res = [], path = []
    const backTracking = (index, sum) => {
        if (sum > n) return -1

        if (path.length == k && sum == n) {
            res.push([...path])
            return -1
        }

        if (path.length >= k) return

        for (let i = index; i <= 9; i++) {
            sum += i
            path.push(i)
            let r = backTracking(i + 1, sum)
            sum -= path.pop()
            if (r == -1) break
        }
    }
    backTracking(1, 0)

    return res
};

// 17.电话号码的字母组合 letterCombinations('23') ==> ["ad","ae","af","bd","be","bf","cd","ce","cf"]
const letterCombinations = function (digits) {
    const numCharMap = {
        2: 'abc',
        3: 'def',
        4: 'ghi',
        5: 'jkl',
        6: 'mno',
        7: 'pqrs',
        8: 'tuv',
        9: 'wxyz'
    }
    const len = digits.length, res = [], path = []
    const backTracking = function (index) {
        if (path.length == len) {
            res.push(path.join(''))
            return
        }
        let str = numCharMap[digits[index]]
        for (let i = 0; i < str.length; i++) {
            path.push(str[i])
            backTracking(index + 1)
            path.pop()
        }
    }
    backTracking(0)
    return res
}

// 93.复原 IP 地址 restoreIpAddresses('25525511135') ==> [ '255.255.11.135', '255.255.111.35' ]
const restoreIpAddresses = function (s) {
    const len = s.length, res = [], path = []

    const backTracking = (index) => {
        // 中止条件
        if (index == len) {
            // 收集结果
            if (path.length == 4) res.push(path.join('.'))
            return
        }

        if (path.length > 3) return

        // 逻辑
        for (let i = index; i < len; i++) {
            // 切割字符串
            const str = s.slice(index, i + 1)
            // 每个整数位于 0 到 255 之间组成，且不能含有前导 0
            if (parseInt(str) > 255 || (str.length > 1 && str[0] == '0')) break;
            path.push(str)
            backTracking(i + 1)
            path.pop()
        }
    }
    backTracking(0)
    return res
}

// 131.分割回文串  partition('aab') ==> [ [ 'a', 'a', 'b' ], [ 'aa', 'b' ] ]
const partition = function (s) {
    const isPalindromeStr = (str) => {
        return str.split('').reverse().join('') == str
    }
    const len = s.length, res = [], path = []
    const backTracking = (index) => {
        if (index == len) {
            res.push([...path])
            return
        }

        for (let i = index; i < len; i++) {
            let str = s.slice(index, i + 1)
            if (!isPalindromeStr(str)) continue
            path.push(str)
            backTracking(i + 1)
            path.pop()
        }
    }

    backTracking(0)

    return res
}

// 491.非递减子序列 findSubsequences([4, 6, 7, 7]) ==> [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
const findSubsequences = function (nums) {
    const len = nums.length, res = [], path = []

    const backTracking = (index, last) => {
        if (path.length > 1) res.push([...path])
        if (index == len) return
        let visited = {}
        for (let i = index; i < len; i++) {
            if ((path.length && last > nums[i]) || visited[nums[i]]) continue
            visited[nums[i]] = true
            path.push(nums[i])
            backTracking(i + 1, nums[i])
            path.pop()
        }
    }

    backTracking(0)
    // console.log(res)
    return res
};

// 47.全排列  permuteUnique([1, 1, 2]) ==> [ [ 1, 1, 2 ], [ 1, 2, 1 ], [ 2, 1, 1 ] ]
const permuteUnique = function (nums) {
    nums.sort((a, b) => a - b)
    const len = nums.length, res = [], path = [], visited = {}
    const backTracking = () => {
        if (path.length == len) {
            res.push([...path])
            return
        }
        for (let i = 0; i < len; i++) {
            if ((i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) || visited[i]) continue
            path.push(nums[i])
            visited[i] = true
            backTracking()
            path.pop()
            visited[i] = false
        }
    }

    backTracking()
    return res
}

// 51.N 皇后 solveNQueens(4) ==> [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
const solveNQueens = function (n) {
    const res = [], cheerBoard = new Array(n).fill(0).map(() => Array(n).fill('.'))
    const isValidate = (row, col) => {
        // 检查列
        for (let i = 0; i < row; i++) {
            if (cheerBoard[i][col] == 'Q') return false
        }
        // 检查左对角线
        for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (cheerBoard[i][j] == 'Q') return false
        }
        // 检查右对角线
        for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (cheerBoard[i][j] == 'Q') return false
        }

        return true

    }

    const backTracking = (row) => {
        if (row == n) {
            res.push([...cheerBoard.map(v => v.join(''))])
            return
        }

        for (let i = 0; i < n; i++) {
            if (!isValidate(row, i)) continue
            cheerBoard[row][i] = 'Q'
            backTracking(row + 1)
            cheerBoard[row][i] = '.'
        }
    }

    backTracking(0)
    return res
};

// 37.解数独
const solveSudoku = function (board) {
    const r = board.length, c = board[0].length

    const isValidate = (row, col, n) => {
        //  判断行是否存在数字
        for (let i = 0; i < c; i++) {
            if (board[row][i] == n) return false
        }
        //  判断列是否存在数字
        for (let i = 0; i < r; i++) {
            if (board[i][col] == n) return false
        }
        //  判断9宫格内是否存在
        let startRow = (Math.floor(row / 3)) * 3,
            startCol = (Math.floor(col / 3)) * 3;
        for (let i = startRow; i < startRow + 3; i++) {
            for (let j = startCol; j < startCol + 3; j++) {
                if (board[i][j] == n) return false
            }
        }
        return true
    }

    const backTracking = function () {
        for (let i = 0; i < r; i++) {
            for (let j = 0; j < c; j++) {
                if (board[i][j] != '.') continue
                for (let n = 1; n <= 9; n++) {
                    if (isValidate(i, j, n)) {
                        board[i][j] = n + ''
                        if (backTracking()) return true
                        board[i][j] = '.'
                    }
                }
                return false
            }
        }
        return true
    }

    backTracking()
};